// https://leetcode.cn/problems/substring-with-concatenation-of-all-words/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        int m = words.size();
        int n = words[0].size();
        int len_s = s.size();

        for (int i = 0; i < n && i + m * n <= len_s; i++) {
            unordered_map<string, int> mp;
            for (int j = 0; j < m; j++) {
                mp[s.substr(i + j * n, n)]++;
            }

            for (string word : words) {
                mp[word]--;
                if (mp[word] == 0) {
                    mp.erase(word);
                }
            }

            for (int k = i; k < len_s - m * n + 1; k += n) {
                if (k != i) {
                    string curWord = s.substr(k + (m - 1) * n, n);
                    mp[curWord]++;
                    if (mp[curWord] == 0) {
                        mp.erase(curWord);
                    }

                    curWord = s.substr(k - n, n);
                    mp[curWord]--;
                    if (mp[curWord] == 0) {
                        mp.erase(curWord);
                    }
                }

                if (mp.empty()) {
                    ans.emplace_back(k);
                }
            }
        }
        return ans;
    }
};